package com.rong.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序，时间复杂度o(n^2)
 * 
 * 选择最小（或者最大的）的数放在最左边
 * 
 * @author liurong
 *
 */
public class SelectSort {

	public static void main(String[] args) {

		int[] sourceArr = { 5, 2, 3, 1 };
		sort(sourceArr);
		System.out.println(Arrays.toString(sourceArr));

		sourceArr = new int[100000];
		for (int i = 0; i < 100000; i++) {
			sourceArr[i] = new Random().nextInt(100000);
		}

		long start = System.currentTimeMillis();
		sort(sourceArr);
		long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	public static void sort(int[] sourceArr) {
		int temp = 0;
		int minNum = 0;
		int minIndex = 0;
		int length = sourceArr.length;
		for (int i = 0; i < length - 1; i++) {
			minNum = sourceArr[i];
			minIndex = i;

			for (int j = i + 1; j < length; j++) {
				if (minNum > sourceArr[j]) {
					minNum = sourceArr[j];
					minIndex = j;
				}
			}

			if (minIndex != i) {
				temp = sourceArr[i];
				sourceArr[i] = sourceArr[minIndex];
				sourceArr[minIndex] = temp;
			}
		}
	}

}
